fast nearest neighbor search disk resid graph purnamrita sarkar andrew moor link predict person graph search fraud detect graph mine problem revolv comput similar node queri node wide class similar measur base random walk graph person pagerank hit commut time simrank fundament problem measur exist onlin algorithm typic examin local neighborhood queri node significantli slower high degre node encount common phenomenon real world graph prove turn high degre node sink result small approxim error greatli improv run time problem comput similar queri time graph larg memori resid obviou solut split graph cluster node store cluster disk page ideal random walk rare cross cluster boundari page fault contribut twofold present effici determinist algorithm find closest neighbor term person pagerank queri node cluster graph develop cluster algorithm rwdisk sequenti sweep data file empir result larg publicli graph dblp cites live journal edg demonstr turn high degre node sink improv run time rwdisk factor boost link predict accuraci factor averag show rwdisk return desir high conduct small size cluster popular cluster algorithm meti requir memori final determinist algorithm comput nearest neighbor incur fewer page fault factor simul random walk 